package 归并排序;

import java.util.Arrays;

public class 归并排序 {
	public static void main(String[] args) {
//		int[] arr = {5,3,4,1,2};
//		
//		int[] temp = new int[arr.length];
//		
//		mergeSort(arr, 0, arr.length-1, temp);
//		
//		System.out.println(Arrays.toString(arr));
		
		
		
		int[] longInt = new int[80000];
		for (int i = 0; i < longInt.length; i++) {
			longInt[i] = (int) (Math.random()*10000);
		}
		
		long star = System.currentTimeMillis();
		
		mergeSort(longInt,0,longInt.length-1,new int[longInt.length]);
		
		long end = System.currentTimeMillis();
		System.out.println((end-star) + "毫秒");		//20~ ms  
		System.out.println((end-star)/1000 + "秒");//0s
		
		
		
	}
	
	/**
	 * 分开 与 合并
	 * @param arr
	 * @param L
	 * @param R
	 */
	public static void mergeSort(int[] arr , int L, int R, int[] temp) {
		//倒过来理解，从底部出发，慢慢向上，将两有序数组合并
		if( L < R) {
			
			
			int M = (L + R)/2;
			//向下分
			mergeSort(arr, L, M, temp);
			//向上合
			mergeSort(arr, M+1, R, temp);
			
			//注意！！！！两个数组有序是前提！！！
			//L是左半边的排好序的L，R是右半边排好序的R，L和R是变动的，L和R之间的距离越来越大
			
			//到此位置，左右两个数组都是有序的，因为分到最小单位之后（长度为1），整个数组就
			//是有序的如arr1=1; arr2=2，此后，经过合并，就算不是最小单位数组，也已经有序	
			//了，理解从下向上
			
			merge(arr,L,M,R,temp);
			//System.out.println("合并("+L+","+R+")");
			
		}
	}
	
	//这个方法单纯排序使用
	//L左边数组起始位置，R右边数组结束位置，M为中间位置，L不超过M，M小于R
	public static void merge(int[] arr, int L, int M, int R,int[] temp) {
		
		//例如：1，2，3，4，5，6，7 ;L = 1;M = 4;R = 6;l = 1;r = 5
        //此时的小r是中间位置+1，第二个数组起始位置，与R不同，R是结束位置
		
		//当前合并数组的左指针
		int l = L;
		//当前合并数组的右指针
		int r = M+1;
		//辅助数组指针
		int t = 0;
		
		//另一种方式的辅助数组
//		int[] tem = new  int[R-L+1];
		
		//------------------------------------------------------
		//也可以在这里面声明一个数组用来暂存排序数组，长度是当前要合并的长度，L和R都是变动的
		//因为下标比实际小一
		//int[] tem = new  int[R-L+1];
		//然后就可以把排好序的数放到tem中
		//等都排好了，把tem放到原始数组中，这样比temp好理解
		//for (int i = 0; i < temp.length; i++) {
        //    arr[i + start] = temp[i];
        //}
		//速度慢一点，但是好理解
		//--------------------------------------------------------
		
		
		//从M位置将数组分成两个，前提是两数组有序！！！！！
		//先把左右两边有序的数据按照规则填充到temp，直到两边数列有一列处理完成
        //while一直判断两个数组是否有一个处理完
		while(l<=M && r<=R) {
			//如果左边数组l小于右边数组r，就将小的那个放到准备好的temp数组中
            //然后移动l和t，注意r没动
			if(arr[l] <= arr[r]) {
				temp[t] = arr[l];
				l++;
				t++;
			}else {
				//else同理，两个数组中小的那个放到temp中
				temp[t] = arr[r];
				r++;
				t++;
			}
		}
		
		//如果两个数组中有一个数组排完序了，因为这两个数组本身就是有序的，所以可以将剩下数组			
		//中的数据直接放在temp后面
		while(l <= M) {
			temp[t] = arr[l];
			t++;
			l++;
		}
		while(r <= R) {
			temp[t] = arr[r];
			t++;
			r++;
		}
		
		
		//-------------------------------------------------------------
		//这个merge()方法是对从L到R中间的数组进行排序，排好序的结果放在temp中，因此
        //需要取出temp中的数组，放回到从L到R的位置上，因为每次L和R都不同。
		//temp数组中的数每一次都是从 0 开始的，虽然它很长但是，不是每次都用完，
		//比如 在 5,3,4,1,2的右边部分，(1,2)进行合并
		//templeft = 3; 3就是数组下标，从3开始到2结束，temp里面排好了( 1,2)的顺序，
		//取出来放到 原始数组的 3 , 4 位置上就好了
		//-------------------------------------------------------------
		
		//理解：取出temp中排好序的结果，还放到原始位置，L和R之间
		t = 0;
		int templeft = L;
		while(templeft <= R) {
			arr[templeft] = temp[t];
			t++;
			templeft++;
		}
		
		//这种方式好理解，具体在上方介绍
//		for (int i = 0; i < tem.length; i++) {
//            arr[i + L] = temp[i];
//        }
		
	}
}
